# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=24
    
    PROBLEM
    
    A permutation is an ordered arrangement of objects. For example, 3124
    is one possible permutation of the digits 1, 2, 3 and 4. If all of the
    permutations are listed numerically or alphabetically, we call it
    lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

    012   021   102   120   201   210

    What is the millionth lexicographic permutation of the digits 0, 1, 2, 3,
    4, 5, 6, 7, 8 and 9?

    
    NOTES
    Tried permutating list as generator recursively splitting heads and tails.
    Ended up adopting simpler method from stackoverflow link below.
    
    
    REFERENCES
    http://stackoverflow.com/a/248854/1093087
    
    
    PERFORMANCE
    time <function solution at 0x7f151408d848>: 2.721008 s
    
"""
#
# Import
#
import time


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    f = "value %s != expected %s"
    f = message != '' and f + " (%s)" or f + "%s"
    assert value == expected, f % (value, expected, message)
    


#
# Test Case / Solution
#
@timeit    
def test_case():
    # test 1: verifying range concatenation
    d0to9 = ''.join(str(d) for d in range(10))
    assert_match(d0to9, '0123456789')
    
    # test 2: problem examples
    numbers = '012'
    expected = ['012', '021', '102', '120', '201', '210']
    permutations = list(permutate(numbers))
    assert_match(permutations, expected)
    
    # test 3: problem case
    permutator = permutate(d0to9)
    perms = [permutator.next() for _ in xrange(1000000)]
    first10 = perms[:10]
    last10 = perms[-10:]
    
    assert_match(sorted(first10), first10)
    assert_match(sorted(last10), last10)
    assert_match(sorted(perms[:5] + perms[-5:]), perms[:5] + perms[-5:])
    assert_match(len(perms), 1000000)

    print "test case passed!"

@timeit
def solution():
    digits = ''.join(str(d) for d in range(10))
    limit = 1000000
    
    permutator = permutate(digits)
    for n in xrange(limit-1):
        permutator.next()
    return permutator.next()

#
# Solution Code
#            
def permutate(string):
    if len(string) == 1:
        yield string
    else:
        for i in xrange(len(string)):
            for permutation in permutate(string[:i] + string[i+1:]):
                yield string[i] + permutation
    
        

#
# Additional Tests
#



#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    